#include <bits/stdc++.h>
using namespace std;
// 函数功能：计算最少步行路段总数
// passengers: 每个站点的乘客数量
// num: 最多可以撤掉的站点数量
int min_step(const vector<int>& passengers, int num) {
    vector<int> p; 
    p.push_back(0); // 最前面虚拟站点，人数为0，方便统一计算左边边界
    p.insert(p.end(), passengers.begin(), passengers.end()); // 插入真实站点
    p.push_back(0); // 最后面虚拟站点，人数为0，方便统一计算右边边界
    int n = p.size(); // 总站点数，包括两个虚拟站点
    // dp[i][j] 表示考虑前 i 个站点，撤掉 j 个站点，并且第 i 个站点保留
    // dp[i][j] = 最少步行路段总数
    vector<vector<int>> dp(n + 1, vector<int>(num + 1, INT_MAX));
    dp[0][0] = 0; // 初始状态：0 个站点，撤掉0个站点，步行距离为0
    // 遍历每个站点 i，表示第 i 个站点保留
    for (int i = 1; i < n; ++i) { 
        // 遍历已经撤掉的站点数量 j
        for (int j = 0; j <= num; ++j) {
            // =======================
            // 情况1：第 i-1 个点也保留
            // 不撤掉任何前面点，步行距离直接继承 dp[i-1][j]
            // =======================
            if (dp[i-1][j] != INT_MAX){
                dp[i][j] = dp[i-1][j];   
            }
            // =======================
            // 情况2：枚举前面连续 k 个点撤掉
            // k 表示连续撤掉的站点数量，1 <= k <= min(j, i-1)
            // 遍历每个可能的连续撤掉长度
            // =======================
            for (int k = 1; k <= j && k <= i - 1; ++k) {
                // 如果撤掉 k 个点之前的状态不可达，跳过
                if (dp[i-k-1][j-k] == INT_MAX) continue;
                int cost = 0; // 存储撤掉这 k 个点的总步行路程
                // 计算这 k 个撤掉站点的步行距离
                // 每个撤掉站点的乘客都会走到最近的保留站点
                for (int t = 1; t <= k; ++t) {
                    int l = (i - k - 1 == 0) ? k - t + 1 : t; // 左边距离
                    int r = (i == n - 1) ? t : k - t + 1;     // 右边距离
                    // 步行距离 = 该站点乘客数 * 到最近保留站点的距离
                    cost += p[i - k + t - 1] * min(l, r);
                }
                // 更新 dp[i][j]，取最小值
                dp[i][j] = min(dp[i][j], dp[i-k-1][j-k] + cost);
            }
        }
    }
    // =======================
    // 最终答案：最后一个真实站点保留，撤掉 num 个点的最少步行距离
    // 注意 dp 下标 n-1 对应最后一个真实站点（虚拟站点 n）
    // =======================
    return dp[n - 1][num];
}
int main() {
    vector<int> passengers = {10, 9, 11, 5, 2};
    int num = 2; // 可以撤掉2个站点
    int ans = min_step(passengers, num);
    cout << ans << endl; // 输出结果
    vector<int> passengers2 = {4, 3, 4, 3, 5, 6, 8};
    num = 3; // 可以撤掉3个站点
    cout << min_step(passengers2, num) << endl; // 输出结果
}
